﻿// ---------------------------------------------------------------------------------------------
// <copyright file="StronglyConnectedComponentFinder.cs" company="Daniel Bradley">
//   Copyright (c) 2015 All Rights Reserved
// </copyright>
// <summary>
//   cf. https://github.com/danielrbradley/CycleDetection
// </summary>
// ---------------------------------------------------------------------------------------------

using System;
using System.Collections.Generic;

namespace Hiyoko.DependenciesSorter.CycleDetection
{
    /// <summary>
    /// Implementation of the Tarjan stronly connected components algorithm.
    /// </summary>
    /// <seealso cref="http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm"/>
    /// <seealso cref="http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph"/>
    public class StronglyConnectedComponentFinder<T>
    {
        #region Private members

        private StronglyConnectedComponentList<T> _stronglyConnectedComponents;
        private Stack<Vertex<T>> _stack;
        private int _index;

        #endregion Private members

        #region Public methods

        /// <summary>
        /// Calculates the sets of strongly connected vertices.
        /// </summary>
        /// <param name="graph">Graph to detect cycles within.</param>
        /// <returns>Set of strongly connected components (sets of vertices)</returns>
        public StronglyConnectedComponentList<T> DetectCycle(IEnumerable<Vertex<T>> graph)
        {
            _stronglyConnectedComponents = new StronglyConnectedComponentList<T>();
            _index = 0;
            _stack = new Stack<Vertex<T>>();
            foreach (var v in graph)
            {
                if (v.Index < 0)
                {
                    StrongConnect(v);
                }
            }
            return _stronglyConnectedComponents;
        }

        #endregion Public methods

        #region Private methods

        private void StrongConnect(Vertex<T> v)
        {
            v.Index = _index;
            v.LowLink = _index;
            _index++;
            _stack.Push(v);

            foreach (Vertex<T> w in v.Dependencies)
            {
                if (w.Index < 0)
                {
                    StrongConnect(w);
                    v.LowLink = Math.Min(v.LowLink, w.LowLink);
                }
                else if (_stack.Contains(w))
                {
                    v.LowLink = Math.Min(v.LowLink, w.Index);
                }
            }

            if (v.LowLink == v.Index)
            {
                var scc = new StronglyConnectedComponent<T>();
                Vertex<T> w;
                do
                {
                    w = _stack.Pop();
                    scc.Add(w);
                } while (v != w);
                _stronglyConnectedComponents.Add(scc);
            }

        }

        #endregion Private methods
    }
}
